package com.jp.algorithm;

public class MaxSubSum {
    public static int[] maxSub(int[] a){
        if(a.length==0)
            return null;
        if(a.length==1)
            return a;

        int maxStart=0;
        int maxEnd=0;
        int maxSum=a[0];

        int curStart=0;
        int curEnd=1;
        for(;curEnd<a.length;){
            int preSum=getSum(curStart,curEnd-1,a);
            if(preSum<=0){
                curStart=curEnd;
                curEnd++;
                continue;
            }
            int curSum=getSum(curStart,curEnd,a);
            if(curSum>maxSum){
                maxSum=curSum;
                maxStart=curStart;
                maxEnd=curEnd;
            }
            curEnd++;
        }
        int[] result = new int[maxEnd-maxStart+1];
        int j=0;
        for(int i=maxStart;i<=maxEnd;i++){
            result[j++]=a[i];
        }
        return result;
    }
    private static int getSum(int start, int end, int[] a){
        int sum=0;
        for(int i=start;i<=end;i++){
            sum+=a[i];
        }
        return sum;
    }


    public static void test(){
        int[] a={-2,1,-3,4,-1,2,1,-5,4};
        int[] result = maxSub(a);

        for(int i=0;i<result.length;i++){
            System.out.println(result[i]);
        }
    }

    public static void main(String[] args) {
        test();
    }
}
